package com.dyz.leetcode._10_slidingWindow;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _30_findSubstring {
    //哈希表
    public List<Integer> findSubstring(String s, String[] words) {
        //统计每个单词出现的次数
        Map<String, Integer> map = new HashMap<>();
        for(String word:words){
            map.put(word, map.getOrDefault(word, 0)+1);
        }

        int oneWordLen = words[0].length();
        int wordNum = words.length;
        int totalLen = wordNum*oneWordLen;
        List<Integer> res = new ArrayList<>();
        for(int i=0; i<s.length()-totalLen+1; i++){
            //拿到等于所有单词长度之和的次数
            String substr = s.substring(i, i+totalLen);
            Map<String, Integer> tmpMap = new HashMap<>();
            for(int j=0; j<totalLen; j+=oneWordLen){
                String oneWord = substr.substring(j, j+oneWordLen);
                tmpMap.put(oneWord, tmpMap.getOrDefault(oneWord, 0)+1);
            }

            //如果单词出现的次数和原始words中单词出现的次数相同，则符合条件
            if(map.equals(tmpMap)){res.add(i);}
        }
            return res;
    }

    //滑动窗口
    public List<Integer> findSubstring1(String s, String[] words) {
        //统计每个单词出现的次数
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        int oneWordLen = words[0].length();
        int wordNum = words.length;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < oneWordLen; i++) {
            int left = i, right = i;
            Map<String, Integer> windowMap = new HashMap<>();
            int matchWords = 0;
            while (right<=s.length()-oneWordLen){
                String  currWord = s.substring(right, right+oneWordLen);
                windowMap.put(currWord, windowMap.getOrDefault(currWord,0)+1);
                matchWords++;
                while (windowMap.getOrDefault(currWord,0)>
                        map.getOrDefault(currWord,0)){
                    String leftWord = s.substring(left, left+oneWordLen);
                    windowMap.put(leftWord, windowMap.getOrDefault(leftWord, 0)-1);
                    left+=oneWordLen;
                    matchWords--;
                }
                if(matchWords==wordNum){res.add(left);}
                right+=oneWordLen;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        Map<String, Integer> map1 = new HashMap<>();
        map.put("q",2);
        map1.put("q", 2);
        System.out.println(map.equals(map1));
    }
}
